#include <iostream>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <sstream>
#include <deque>

using namespace std;

typedef long long int64;

set<int64> hash;
set<int> enable;

int n;

int mark[100];
int invalid[100];

#define two(x) (1 << int64(x))

#define incmark(x) ++mark[(x)]; if (mark[(x)] == 1) enable.insert((x));
#define decmark(x) --mark[(x)]; if (mark[(x)] == 0) enable.erase((x));

void add(int k)
{
	invalid[n * n - k - 1] = true;
	enable.erase(k);
	int x = k / n;
	int y = k - x * n;
	if (x > 0)
		incmark(k - n);
	if (x < n - 1)
		incmark(k + n);
	if (y > 0)
		incmark(k - 1);
	if (y < n - 1)
		incmark(k + 1);
}

void remove(int k)
{
	invalid[n * n - k - 1] = false;
	enable.insert(k);
	int x = k / n;
	int y = k - x * n;
	if (x > 0)
		decmark(k - n);
	if (x < n - 1)
		decmark(k + n);
	if (y > 0)
		decmark(k - 1);
	if (y < n - 1)
		decmark(k + 1);
}

int validCount;

void DFS(int64 s, int cnt)
{
	if (cnt == n * n / 2)
	{
		++validCount;
		if (validCount % 10000 == 0)
			cout << validCount << endl;
#if 0
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			    cout << ((s >> (i * n + j)) & 1);
			cout << endl;
		}
		cout << endl;
#endif
		return;
	}
	if (hash.find(s) != hash.end())
		return;
	hash.insert(s);
	vector<int> x;
	for (set<int>::iterator it = enable.begin(); it != enable.end(); ++it)
		if (!invalid[*it])
			x.push_back(*it);
		
	for (int i = 0; i < x.size(); ++i)
	{
		add(x[i]);
		DFS(s | two(x[i]), cnt + 1);
		remove(x[i]);
	}
}

int main()
{
	n = 6;
	hash.clear();
	enable.clear();
	enable.insert(0);
	
	memset(mark, 0, sizeof(mark));
	memset(invalid, 0, sizeof(invalid));
	mark[0] = 1;
	
	add(0);
	DFS(two(0), 1);
	cout << validCount << endl;
	getc(stdin);
	return 0;
}
